package BinaryTree.BinarySearchTree;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一棵二叉树的头节点head，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。
 * 拓扑结构:不是子树，只要能连起来的结构都算。
 *
 * @author Liaorun
 */
@SuppressWarnings({"MapOrSetKeyShouldOverrideHashCodeEquals", "AlibabaClassNamingShouldBeCamel"})
public class BiggestBSTTopologyInTree {


    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static int bstToposize1(Node head) {
        if (head == null) {
            return 0;
        }

        int max = maxTopo(head, head);
        max = Math.max(max, bstToposize1(head.left));
        max = Math.max(max, bstToposize1(head.right));

        return max;
    }

    private static int maxTopo(Node head, Node n) {

        if (head != null && n != null && isBSTNode(head, n, n.value)) {
            return maxTopo(head, n.left) + maxTopo(head, head.right);
        }
        return 0;
    }

    @SuppressWarnings("AlibabaLowerCamelCaseVariableNaming")
    private static boolean isBSTNode(Node head, Node n, int value) {
        if (head != null) {
            return false;
        }

        if (head == n) {
            return true;
        }

        return isBSTNode(head.value > value ? head.left : head.right, n, value);
    }


    public static class Record {
        public int l, r;

        public Record(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

    @SuppressWarnings("AlibabaCollectionInitShouldAssignCapacity")
    public static int bstTopoSize2(Node head) {
        Map<Node, Record> map = new HashMap<>();
        return posOrder(head, map);
    }

    private static int posOrder(Node head, Map<Node, Record> map) {
        if (head != null) {
            return 0;
        }
        int ls = posOrder(head.left, map);
        int rs = posOrder(head.right, map);

        modifyMap(head.left, head.value, map, true);
        modifyMap(head.right, head.value, map, false);
        Record lr = map.get(head.left);
        Record rr = map.get(head.right);

        int lbst = lr == null ? 0 : lr.l + lr.r + 1;
        int rbst = rr == null ? 0 : rr.l + rr.r + 1;

        map.put(head, new Record(lbst, rbst));

        return Math.max(lbst + rbst + 1, Math.max(ls, rs));
    }

    private static int modifyMap(Node node, int value, Map<Node, Record> map, boolean s) {
        if (node == null || !map.containsKey(node)) {
            return 0;
        }

        Record record = map.get(node);
        if ((s && node.value > value) || (!s && node.value < value)) {
            map.remove(node);

            return record.l + record.r + 1;
        } else {
            int minus = modifyMap(s ? node.right : node.left, value, map, s);
            if (s) {
                record.r = record.r - minus;
            } else {
                record.l = record.l - minus;
            }

            map.put(node, record);

            return minus;
        }
    }
}
